package com.example.lcpractice.lc;

import com.example.lcpractice.datastructure.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * [39]组合总和.java
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的
 * 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * <p>
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * <p>
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * <p>
 * 示例 1：
 * <p>
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 * 解释：
 * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 * 7 也是一个候选， 7 = 7 。
 * 仅有这两种组合。
 * <p>
 * 示例 2：
 * <p>
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 * <p>
 * 示例 3：
 * <p>
 * 输入: candidates = [2], target = 1
 * 输出: []
 * <p>
 * 提示：
 * <p>
 * 1 <= candidates.length <= 30
 * 1 <= candidates[i] <= 200
 * candidate 中的每个元素都 互不相同
 * 1 <= target <= 500
 * <p>
 * Related Topics 数组 回溯 👍 2126 👎 0
 */
public class Lc39 {
    public static void main(String[] args) {
//        ListNode list = ListNode.getSingleLinkedList();
//        ListNode list2 = ListNode.getSingleLinkedList2();
//        System.out.println(mergeTwoLists(list2, list2));
        System.out.println(combinationSum(new int[]{2, 3, 6, 7}, 7));
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> answer = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        dfs(candidates, target, answer, temp, 0);
        return answer;
    }

    /**
     * @param candidates 可以抽取数字的候选数组
     * @param target     组合的目标数字不断减去临时list已有的和，尚需凑够的数字，-1代表临时list内已经 超过，0代表正好，临时list合理组合
     * @param ans        组合结果数组
     * @param tmp        记录一个组合的临时list
     * @param idx
     */
    public static void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> tmp, int idx) {
        //已有的组合和已经超过尚需数字
        if (target < 0) {
            return;
        }
        //已有的组合恰好和为目标，记录下排列组合
        else if (target == 0) {
            // ☆☆☆切记此处要new 一个list否则引用对象始终只有这个temp
            ans.add(new ArrayList<Integer>(tmp));
            return;
            //已有的组合还不够
        } else {
            //递归中每一次都要对候选数组遍历选取，再进行递归，每次选取递给下一层次后，记得移除元素，对引用对象temp回溯
            // 为什么要从idx开始，确保可以有多个自身比如[2,2,2]=6
            // 如果没有idx，从0开始，就会
            // [2,3,6,7]
            //    ↑
            // [2,3,6,7]
            //  ↑
            // [2,3,6,7]
            //  ↑
            //形成重复结果
            //正确是第一次已经考虑这个结果了
            // [2,3,6,7]
            //  ↑
            // [2,3,6,7]
            //  ↑
            // [2,3,6,7]
            //    ↑
            for (int i = idx; i < candidates.length; i++) {
                tmp.add(candidates[i]);
                dfs(candidates, target - candidates[i], ans, tmp, i);
                //回溯，上一步已经对加入元素candidates[i]的组合进行逻辑处理
                //这一步移除，元素
                tmp.remove(tmp.size() - 1);
            }
            return;
        }
    }


}
